//
// Created by WangBlue(wangjiping596@gmail.com) on 2025/10/8.
//  @file myCharKMP.c
//  @desc 基于 myChar 类型实现 KMP 字符串匹配算法
//        支持教材版本（1-based，下标从1）和实际版本（0-based，下标从0）
//  @author WangBlue(wangjiping596@gmail.com)
//  @date 2025-10-08
//  @version 1.0
//
#include <stdio.h>

#define MAX_SIZE 100  ///< myChar 最大容量

// ------------------------- 类型定义 -------------------------

/**
 * @struct myChar
 * @brief 自定义字符串类型
 *
 * - ch[MAX_SIZE] : 字符数组
 * - length       : 当前字符串长度
 *
 * @note 教材版本习惯使用 1-based 下标，实际版本使用 0-based 下标
 */
typedef struct myChar {
    char ch[MAX_SIZE];  ///< 字符数组
    int length;         ///< 当前长度
} myChar;

// ------------------------- next 数组生成函数 -------------------------

/**
 * @brief 教材版本：生成模式串 p 的 next 数组（1-based）
 * @param p 模式串
 * @param next 输出 next 数组
 * @note
 *   - next[i] 表示模式串 p[1..i-1] 的最长相等前后缀长度
 *   - 教材算法中，字符串下标从 1 开始
 */
void getNextBase1(myChar *p, int next[]) {
    if (p == NULL || p->length == 0) return;

    int i = 1;      // 当前计算 next[i]
    int j = 0;      // 当前匹配前缀长度
    next[1] = 0;    // 第 1 个字符没有前缀后缀

    while (i < p->length) {  // 1-based 循环到 length-1
        if (j == 0 || p->ch[i] == p->ch[j]) {
            i++;
            j++;
            next[i] = j;  // 保存当前最长前后缀长度
        } else {
            j = next[j]; // 回退到上一个最长匹配长度
        }
    }
}

/**
 * @brief 实际版本：生成模式串 p 的 next 数组（0-based）
 * @param p 模式串
 * @param next 输出 next 数组
 * @note
 *   - next[i] 表示模式串 p[0..i-1] 的最长相等前后缀长度
 *   - 实际使用版本，方便 C 语言数组下标
 */
void getNextBase0(myChar *p, int next[]) {
    if (p == NULL || p->length == 0) {
        printf("empty list\n");
        return;
    }
    int i = 0, j = -1;
    next[0] = -1; // 第 0 个元素没有前缀后缀
    while (i < p->length - 1) {
        if (j == -1 || p->ch[i] == p->ch[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j]; // 回退
        }
    }
}

// ------------------------- KMP 匹配函数 -------------------------

/**
 * @brief 教材版本 KMP 匹配（1-based）
 * @param text 主串
 * @param p 模式串
 * @param next 模式串的 next 数组
 * @return 匹配位置（1-based），未匹配返回 -1
 */
int indexKMPBase1(myChar *text, myChar *p, int next[]) {
    if (p == NULL || p->length == 0) return -1;
    if (p->length > text->length) return -1;

    getNextBase1(p, next);

    int i = 1;  // 主串指针（1-based）
    int j = 1;  // 模式串指针（1-based）

    while (i <= text->length && j <= p->length) {
        if (j == 0 || text->ch[i] == p->ch[j]) {
            i++;
            j++;
        } else {
            j = next[j]; // 回退模式串指针
        }
    }

    return (j > p->length) ? (i - p->length) : -1;
}

/**
 * @brief 实际版本 KMP 匹配（0-based）
 * @param text 主串
 * @param p 模式串
 * @param next 模式串的 next 数组
 * @return 匹配位置（0-based），未匹配返回 -1
 */
int indexKMPBase0(myChar *text, myChar *p, int next[]) {
    if (p == NULL || p->length == 0) return -1;
    if (p->length > text->length) return -1;

    getNextBase0(p, next);

    int i = 0; // 主串指针（0-based）
    int j = 0; // 模式串指针（0-based）

    while (i < text->length && j < p->length) {
        if (j == -1 || text->ch[i] == p->ch[j]) {
            i++;
            j++;
        } else {
            j = next[j]; // 回退模式串指针
        }
    }

    return (j == p->length) ? (i - p->length) : -1;
}

// ------------------------- 测试主函数 -------------------------

int main() {
    // ---------------- 教材版本测试 ----------------
    myChar text1;  // abcababc
    text1.ch[1] = 'a';
    text1.ch[2] = 'b';
    text1.ch[3] = 'c';
    text1.ch[4] = 'a';
    text1.ch[5] = 'b';
    text1.ch[6] = 'a';
    text1.ch[7] = 'b';
    text1.ch[8] = 'c';
    text1.length = 8;

    myChar pattern1;  //ababc
    pattern1.ch[1] = 'a';
    pattern1.ch[2] = 'b';
    pattern1.ch[3] = 'a';
    pattern1.ch[4] = 'b';
    pattern1.ch[5] = 'c';
    pattern1.length = 5;

    int next1[pattern1.length + 1];
    int pos1 = indexKMPBase1(&text1, &pattern1, next1);
    if (pos1 != -1) {
        printf("Pattern found at position %d (1-based)\n", pos1);
    } else {
        printf("Pattern not found (1-based)\n");
    }

    // ---------------- 实际版本测试 ----------------
    myChar text0 = {"abcababc", 8};
    myChar pattern0 = {"ababc", 5};
    int next0[pattern0.length];

    int pos0 = indexKMPBase0(&text0, &pattern0, next0);
    if (pos0 != -1) {
        printf("Pattern found at position %d (0-based)\n", pos0);
    } else {
        printf("Pattern not found (0-based)\n");
    }

    return 0;
}
